/*ver 0.1 made by Jeroen S and W 
 * implemented methods of interface Build
 * ver 0.2 - 02-01-2008 - by Jeroen S
 * Minor bugfixes and other cleanup
 * ver 0.3 - 02-01-2008 - by Jeroen S
 *  Resolved issues with operators that caused issues with 
 *  non-square mazes
 *  ver: 0.4, date 3-1-2008 by Jeroen S
 *  Made selecting a partner more random (no more clockwise
 *  moving through the directions)
 * 
 *   ver:0.5 , date 4-1-2008 by Jeroen W
 *  isolated coordinatepair in other class
 * 
 * 
 */



package mazeAssignment;

import java.util.ArrayList;

public class PathBuild implements Build{

	private Maze mazeGrid;
	private ArrayList<CoordinatePair> notVisited, visited;

	//returns the maze
	public Maze getMaze() {
		return mazeGrid;
		
	}
	
	//returns true if the element is not visited.
	private boolean elementNotVisited(int x, int y)
	{
		for(int i = 0; i < notVisited.size(); i++)
		{
			CoordinatePair p = notVisited.get(i);
			if(p.x == x && p.y == y)
				return true;
		}
		return false;
	}
	
	//searches the index of the element
	private int findElement(int x, int y)
	{
		for(int i = 0; i < notVisited.size(); i++)
		{
			CoordinatePair p = notVisited.get(i);
			if(p.x == x && p.y == y)
				return i;
		}
		return -1;
	}

	//initialise the extra structures that are required for this algorithm:
	//2 arraylists: visited and not visited.
	public void initialise(Maze maze) {
		mazeGrid=maze;
		int x= mazeGrid.getSizeX();
		int y= mazeGrid.getSizeY();
		notVisited = new ArrayList<CoordinatePair>();
		visited = new ArrayList<CoordinatePair>();
		//set the coordinatepairs for the positions.
		for(int i=0; i<(x*y); i++)
		{ 
			CoordinatePair p = new CoordinatePair(i/y, i%y);
			notVisited.add(p);
		}
		int i= (int)(Math.random()*notVisited.size());
		visited.add(notVisited.get(i));
		notVisited.remove(i);
		
		//set start and endpoint
		MazeElement start = mazeGrid.getElement(0, 0);
		//start.setNorth(false);
		//start.setWest(false);
		start.setSolveState(MazeElement.SOLVE_START);
		MazeElement end = mazeGrid.getElement(x-1, y-1);
		//end.setSouth(false);
		//end.setEast(false);
		end.setSolveState(MazeElement.SOLVE_END);
		
	}

	//returns true if notVisited is the appropiate size (0)
	public boolean isDone() {
		return (notVisited.size()<1);
	}

	//advances the algorithm by one step.
	public boolean tick() {
		if(isDone())
		{
			return false;
		}
		
		boolean tickIsDone = false;
		
		//the tick is based on trial and error, we should repeat this until the tick was succesful
		while (!tickIsDone)
		{
			//take a visited element
			int i= (int)(Math.random()*visited.size());
			CoordinatePair firstPair= (CoordinatePair) visited.get(i);
			
			//find a partner (geen partner, verwijder uit visited en ga weer een nieuwe zoeken)
			boolean foundPartner= false;
			int numpartners = 0;
			boolean doneNorth = false;
			boolean doneEast = false;
			boolean doneSouth = false;
			boolean doneWest = false;
			int partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
			
			//search for a pair that is aside the firstPair, and registered in notVisited
			//if none can be found amongside the firstElement
			//then it is time to try to find another one.
			//there are tests for (in order:) out of bounds, same group)
			//as soon as one is found, the wall is taken down and it is removed from notVisited
			//and added to visited
			//at the end firstPair is removed from visited so it will not be used again.

			while (!foundPartner && numpartners < 4)
			{
				
				switch (partner)
				{
				//0 = north
				case 0: 
					doneNorth = true;
					if(firstPair.y==0)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(firstPair.x, firstPair.y-1))
					{
						foundPartner = true;
						mazeGrid.getElement(firstPair.x, firstPair.y-1).setSouth(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setNorth(false);
						notVisited.remove(findElement(firstPair.x, (firstPair.y)-1));
						visited.add(new CoordinatePair(firstPair.x, (firstPair.y)-1));
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//1= east
				case 1:	
					doneEast = true;
					if(firstPair.x==mazeGrid.getSizeX()-1)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(firstPair.x+1, firstPair.y))
					{
						foundPartner = true;
						mazeGrid.getElement(firstPair.x+1, firstPair.y).setWest(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setEast(false);
						notVisited.remove(findElement((firstPair.x)+1, firstPair.y));
						visited.add(new CoordinatePair((firstPair.x)+1, firstPair.y));
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//2= south
				case 2:	
					doneSouth = true;
					if(firstPair.y==mazeGrid.getSizeY()-1)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(firstPair.x, (firstPair.y)+1))
					{
						mazeGrid.getElement(firstPair.x, firstPair.y+1).setNorth(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setSouth(false);
						notVisited.remove(findElement(firstPair.x, (firstPair.y)+1));
						visited.add(new CoordinatePair(firstPair.x, (firstPair.y)+1));

						foundPartner = true;
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//3= west
				case 3:	
					doneWest = true;
					if(firstPair.x==0)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(firstPair.x-1, (firstPair.y)))
					{
						foundPartner = true;
						mazeGrid.getElement(firstPair.x-1, firstPair.y).setEast(false);
						mazeGrid.getElement(firstPair.x, firstPair.y).setWest(false);
						notVisited.remove(findElement(firstPair.x-1, (firstPair.y)));
						visited.add(new CoordinatePair(firstPair.x-1, (firstPair.y)));
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				case -1:
					numpartners = 4;
					break;
				}
				
			}
			//if all walls have been searched, then it is time for a new element to checkup!
			if(numpartners > 3)
			{
				visited.remove(firstPair);
				continue;
			}
			tickIsDone = true;
			
		}
		//report tick is done
		return true;
	}
	
	// Selects a random partner, based on the available choices.
	private int selectPartner(boolean doneNorth, boolean doneEast, boolean doneSouth, boolean doneWest)
	{
		int numchoices = 0;
		
		// No partners left to do?
		if(doneNorth && doneEast && doneSouth && doneWest)
			return -1;
		
		// Add a choice for each still unchecked partner.
		if(!doneNorth)
			numchoices++;
		if(!doneEast)
			numchoices++;
		if(!doneSouth)
			numchoices++;
		if(!doneWest)
			numchoices++;
		
		// Choose
		int choice = (int) (Math.random() * numchoices);
		
		// If a partner is available, it was added to the choices
		if(!doneNorth)
		{
			// This is our choice
			if(choice == 0)
				return 0;
			// Prepare for the next
			else
				choice--;
		}
		if(!doneEast)
		{
			if(choice == 0)
				return 1;
			else
				choice--;
		}
		if(!doneSouth)
		{
			if(choice == 0)
				return 2;
			else
				choice--;
		}
		if(!doneWest)
		{
			if(choice == 0)
				return 3;
			else
				choice--;
		}
		/*!NOTREACHED*/
		return -1;
	}
	
}
